#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/10/17 20:17|20:17
# @Author  : yangdingyi
# @File    : 2020-10-17.52.N皇后 II
# @Software: PyCharm
from tools.my_methods import *


class Solution:
    def __init__(self):
        self.ans = 0

    def totalNQueens(self, n: int) -> int:
        # rs = [0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680]
        # return rs[n]
        self.ans = 0
        qq = [-1 for i in range(n)]
        qs = [0 for i in range(n)]

        def test(x, qqq, dq):
            for xx in range(dq):
                if dq-xx == x-qqq[xx] or dq-xx == qqq[xx]-x:
                    return False
            return True

        def dfs(nn, dep=0):
            if dep >= nn:
                self.ans += 1
                return
            for x in range(nn):
                if qs[x] == 0:
                    if test(x, qq, dep):
                        qq[dep], qs[x] = x, 1
                        dfs(nn, dep+1)
                        qs[x] = 0
            return
        dfs(n)

        return self.ans


questions = [
    (0,),
    (1,),
    (4,),
    (5,),
    (6,),
    (10,),
]

work(questions, lambda q: Solution().totalNQueens(q[0]))
